package binarytree

// import "container/ring"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
// 找出两个节点的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 当前节点左右子树中存在p q 则当前节点就是公共祖先   带上深度值，判断是否是最近的
	// 自底向上查找 用后序遍历 
	// 使用后序遍历，回溯的过程，就是从低向上遍历节点，一旦发现如何这个条件的节点，就是最近公共节点了。
	if root == nil || root == q || root == p {
		return root   //如果找到了 节点p或者q，或者遇到空节点，就返回。
	}

	// 确定单层逻辑
	// 左 右
	left := lowestCommonAncestor(root.Left,p,q)
	right := lowestCommonAncestor(root.Right,p,q)
	// 中 处理其左右的情况
	if left!=nil{
		if right!=nil {
			return root
		}
		return left  // 目标节点通过left返回
	}
	// 说明目标节点通过right返回
	return right
}
